import java.util.*;
public class Test {
    /*
    题目1：斐波那契凤尾
     */
    //NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
    //为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。
    // 当然，斐波那契数会很大。
    // 因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。(这里隐含了补0的信息！)
    //为了通过所有用例，不可以每个n都算一遍，这样会超时，只能以空间换时间了
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] fab = new int[100001];
        fab[0] = 1;
        fab[1] = 1;
        int flag = 0;
        int x = 0;
        for(int i = 2; i <= 100000; i++){
            int ret = (fab[i - 1] + fab[i - 2]);
            if(flag == 0 && ret >= 1000000){
                flag = i;
            }
            fab[i] = ret % 1000000;

        }
        while(sc.hasNext()){
            int n = sc.nextInt();
            if(n <= flag){
                System.out.print(fab[n] + " ");
            }else{
                System.out.printf("%06d",fab[n]);
            }
        }
    }

}
